package org.zjt.tree;



import java.util.ArrayDeque;
import java.util.Stack;

/**
 * @author juntao.zhang
 * @version V1.0
 * @Description:
 *
 *      深度遍历:   stack
 *
 *      广度遍历:   deque数组
 *
 * @Package org.zjt.tree
 * @date 2018/11/11 20:57
 */
public class BinaryTree {

    static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value){
            this.value=value;
        }
    }


    public static void main(String[] args) {
        int[] array = new int[]{1,2,5,3,54,34,3,43,7,87,24,58};

        TreeNode root = makeBinaryTree(array,0);

        deepShow(root);

        weightShow(root);

        weightShow2(root);
    }

    /**
     * 根据广度遍历生成二叉树
     * @param array
     * @param index
     * @return
     */
    private static TreeNode makeBinaryTree(int[] array,int index) {
        if (index >= array.length){
            return null;
        }
        TreeNode root = new TreeNode(array[index]);
        root.left = makeBinaryTree(array,index * 2 +1);
        root.right = makeBinaryTree(array,index * 2+2);
        return root;
    }


    /**
     * 深度遍历:  栈
     * @param root
     */
    public static void deepShow(TreeNode root) {
        Stack<TreeNode> treeNodes = new Stack<>();
        treeNodes.push(root);
        while(!treeNodes.isEmpty()){
            TreeNode node=treeNodes.pop();
            System.out.print(node.value+"    ");
            if(node.right!=null){
                treeNodes.push(node.right);
            }
            if(node.left!=null){
                treeNodes.push(node.left);
            }
        }
       System.out.println();
    }


    /**
     * 广度遍历     队列
     * @param root
     */
    public static void weightShow(TreeNode root) {
        ArrayDeque<TreeNode> treeNodeArrayDeque = new ArrayDeque<TreeNode>();
        treeNodeArrayDeque.add(root);
        while (!treeNodeArrayDeque.isEmpty()){
            TreeNode node=treeNodeArrayDeque.remove();
            System.out.print(node.value+"    ");

            if(node.left!=null){
                treeNodeArrayDeque.add(node.left);
            }
            if(node.right!=null){
                treeNodeArrayDeque.add(node.right);
            }
        }
        System.out.println();
    }

    /**
     * 广度遍历  ：
     *      偶数行：从左到右。
     *      奇数行：从右到左
     *
     * @param root
     */
    public static void weightShow2(TreeNode root) {
        ArrayDeque<TreeNode> treeNodeArrayDeque = new ArrayDeque<>();
        treeNodeArrayDeque.add(root);

        int num = 0;
        while (!treeNodeArrayDeque.isEmpty()){
            TreeNode node = treeNodeArrayDeque.remove();
            System.out.print(node.value+"    ");
            if (num % 2 == 0){
                if(node.left!=null){
                    treeNodeArrayDeque.add(node.left);
                }
                if(node.right!=null){
                    treeNodeArrayDeque.add(node.right);
                }
            }else{
                if(node.right!=null){
                    treeNodeArrayDeque.add(node.right);
                }
                if(node.left!=null){
                    treeNodeArrayDeque.add(node.left);
                }
            }
            num ++;
        }
        System.out.println();
    }
}
